package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import org.omg.CORBA.PUBLIC_MEMBER;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author Fengkai
 * @creat 2023/3/30
 * 输入一个长度为4的倍数的字符串，字符串中仅包含WASD四个字母。
 * 将这个字符串中的连续子串用同等长度的仅包含WASD的字符串替换，如果替换后整个字符串中WASD四个字母出现的频数相同，那么我们称替换后的字符串是“完美走位”。
 */
public class PerFectWASD {


    public static void main (String[] args) {
        for (int i = 0; i < 100; i++) {
            String str = getSrt();
            long l = System.currentTimeMillis();
            int i2 = myMthod(str);
            long s = System.currentTimeMillis();

            long a = System.currentTimeMillis();
            int i1 = hisMethod(str);
            long b = System.currentTimeMillis();
            System.out.println("myMthod(str)耗时" + (s - l) + ",hisMethod(str)耗时:" + (b - a));
            System.out.println(i2 == i1);
        }
//        System.out.println(myMthod("WWWWWASSSSSDDDDD"));
//        System.out.println(hisMethod("AAAA"));
    }

    private static String getSrt () {
        ArrayList<String> strings = new ArrayList<>();
        strings.add("A");
        strings.add("W");
        strings.add("S");
        strings.add("D");
        int i = (int) ((Math.random() * 25000) + 1) * 4;
        StringBuilder stringBuilder = new StringBuilder("");
        for (int j = 0; j < i; j++) {
            stringBuilder.append(strings.get((int) (Math.random() * 3 + 1)));
        }
        return stringBuilder.toString();
    }

    public static int myMthod (String input) {
        HashMap<Character, Integer> countMap = new HashMap<>();
        countMap.put('W', 0);
        countMap.put('A', 0);
        countMap.put('S', 0);
        countMap.put('D', 0);
        for (int i = 0; i < input.length(); i++) {
            countMap.put(input.charAt(i), countMap.getOrDefault(input.charAt(i), 0) + 1);
        }
        if (countMap.get('W') == countMap.get('A') && countMap.get('W') == countMap.get('S') && countMap.get('W') == countMap.get('D')) {
            return 0;
        }
        int equals = input.length() / 4;
        //找到其中一个或者两个字母出现次数多了
        HashMap<Character, Integer> overMap = new HashMap<>();
        for (Map.Entry<Character, Integer> stringIntegerEntry : countMap.entrySet()) {
            if (stringIntegerEntry.getValue() > equals) {
                overMap.put(stringIntegerEntry.getKey(), stringIntegerEntry.getValue());
            }
        }
        //只有一个字母多  就替换以该字母开始 并以该字母结尾 包含相当于多出数量的该字母子串
        if (overMap.size() == 1) {
            Set<Character> strings = overMap.keySet();
            Character over = strings.stream().findFirst().get();
            Integer count = overMap.get(over) - equals;
            if (count == 1) {
                return 1;
            }
            int length = Integer.MAX_VALUE;
            Integer sum = 0;
            for (int i = 0; i < input.length() - count; i++) {
                if (input.charAt(i) == over) {
                    sum++;
                }
                for (int j = i + 1; j < input.length(); j++) {
                    if (input.charAt(j) == over) {
                        sum++;
                        if (sum == count) {
                            length = Math.min(length, j - i + 1);
                        }
                    }
                    if (j == input.length() - 1) {
                        sum = 0;
                    }
                }
            }
            return length;
        }

        if (overMap.size() == 2) {
            Set<Character> strings = overMap.keySet();
            Object[] stringsst = strings.toArray();
            Character over1 = (Character) stringsst[0];
            Character over2 = (Character) stringsst[1];

            Integer count1 = overMap.get(over1) - equals;
            Integer count2 = overMap.get(over2) - equals;
            int length = Integer.MAX_VALUE;
            Integer sum1 = 0;
            Integer sum2 = 0;
            int left = 0;
            int right = 0;
            while (true){
                for (int i = left; i <= right; i++) {
                    if (input.charAt(i) == over1){
                        sum1++;
                    }else if (input.charAt(i) == over2) {
                        sum2++;
                    }
                }
                if (sum1 >= count1 && sum2 >= count2){
                    length = Math.min((right - left + 1), length);
                    sum1 = 0;
                    sum2 = 0;
                    left ++;
                }else {
                    sum1 = 0;
                    sum2 = 0;
                    right ++;
                }
                if (right >= input.length()){
                    break;
                }
            }

            return length;
        }

        if (overMap.size() == 3) {
            Set<Character> strings = overMap.keySet();
            Object[] stringsst = strings.toArray();
            Character over1 = (Character) stringsst[0];
            Character over2 = (Character) stringsst[1];
            Character over3 = (Character) stringsst[2];

            Integer count1 = overMap.get(over1) - equals;
            Integer count2 = overMap.get(over2) - equals;
            Integer count3 = overMap.get(over3) - equals;
            int length = Integer.MAX_VALUE;
            Integer sum1 = 0;
            Integer sum2 = 0;
            Integer sum3 = 0;
            int left = 0;
            int right = 0;
            while (true){
                for (int i = left; i <= right; i++) {
                    if (input.charAt(i) == over1){
                        sum1++;
                    }else if (input.charAt(i) == over2) {
                        sum2++;
                    } else if (input.charAt(i) == over3) {
                        sum3++;
                    }
                }
                if (sum1 >= count1 && sum2 >= count2 && sum3 >= count3){
                    length = Math.min((right - left + 1), length);
                    sum1 = 0;
                    sum2 = 0;
                    sum3 = 0;
                    left ++;
                }else {
                    sum1 = 0;
                    sum2 = 0;
                    sum3 = 0;
                    right ++;
                }
                if (right >= input.length()){
                    break;
                }
            }
            return length;
        }
        return -1;
    }

    public static int hisMethod (String input_str) {
        //预设值
        Map<Character, Integer> char_count = new HashMap<Character, Integer>();

        //遍历字符串
        for (int i = 0; i < input_str.length(); i++) {
            char key = input_str.charAt(i);

            if (char_count.get(key) == null) {
                char_count.put(key, 1);
            } else {
                char_count.put(key, char_count.get(key) + 1);
            }
        }

        //遍历WASD,防止输入没有这三个字符
        for (int i = 0; i < "WASD".length(); i++) {
            char key = "WASD".charAt(i);

            if (char_count.get(key) == null) {
                char_count.put(key, 0);
            }
        }


        // 特殊情况
        if (char_count.get('W') == char_count.get('A') &&
                char_count.get('W') == char_count.get('S') &&
                char_count.get('W') == char_count.get('D')) {
            return 0;
        }

        // 左右区间位置
        int left = 0;
        int right = 0;
        int length = 0;

        // 替换的最小长度
        int res = input_str.length();
        // 出现次数最多的字母
        int max_char_num = 0;
        // 可替换字母个数, 随着指针移动，如果free_char_num 大于0且能被4整除，当前范围满足条件，左指针右移一格，否则右指针右移
        int free_char_num = 0;

        char_count.put(input_str.charAt(0), char_count.get(input_str.charAt(0)) - 1);
        while (true) {
            max_char_num = Math.max(Math.max((Math.max(char_count.get('W'), char_count.get('S'))), char_count.get('A')), char_count.get('D'));
            length = right - left + 1;
            free_char_num = length - ((max_char_num - char_count.get('W')) + (max_char_num - char_count.get('S')) + (max_char_num - char_count.get('A')) + (max_char_num - char_count.get('D')));
            if (free_char_num >= 0 && free_char_num % 4 == 0) {
                if (length < res) {
                    res = length;
                }
                char_count.put(input_str.charAt(left), char_count.get(input_str.charAt(left)) + 1);
                left++;

            } else {
                right++;
                if (right >= input_str.length())// 越界即结束
                    break;
                char_count.put(input_str.charAt(right), char_count.get(input_str.charAt(right)) - 1);
            }

            if (right >= input_str.length())// 越界即结束
                break;
        }
        return res;
    }

}
